package com.xigua._树;

import com.xigua.TreeNode;

import java.awt.*;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 * @date 2022/4/2811:12
 */
public class _110_平衡二叉树 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,null,new TreeNode(2,null,new TreeNode(3)));
        System.out.println(isBalanced1(root));
    }

    public static boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        if (Math.abs(getHeight(root.left)-getHeight(root.right)) > 1) return false;
        return isBalanced(root.left)&& isBalanced(root.right);
    }

    static Integer getHeight(TreeNode root){
        if (root == null) return 0;
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }


    public static boolean isBalanced1(TreeNode root) {
        return height(root) >= 0;
    }

    static int height(TreeNode root) {
        if (root == null ) return 0;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (rightHeight == -1 ||leftHeight == -1 || Math.abs(rightHeight-leftHeight)>1 ){
            return -1;
        }else {
            return Math.max(leftHeight,rightHeight)+1;
        }
    }


}
